package heap.shiftDown;

import sortingAdvance.quickSort.InsertionSort;
import sortingAdvance.quickSort.SortTestHelper;

import java.util.Arrays;

public class MergeSort {

    public static void sort(Comparable[] arr) {
        int length = arr.length;
        sort(arr, 0, length - 1);
    }

    private static void sort(Comparable[] arr, int l, int r) {
        if(r - l <= 16) {
           InsertionSort.sort(arr, l, r);
           return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        if(arr[mid].compareTo(arr[mid + 1]) > 0)
            merge(arr, l, mid, r);
    }

    private static void merge(Comparable[] arr, int l, int mid, int r) {
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1); // 开辟一个临时空间
        int m = l;
        int n = mid + 1;
        for(int i = l; i <= r; i++) {
            if(m > mid) {
                arr[i] = aux[n - l];
                n++;
            } else if (n > r) {
                arr[i] = aux[m - l];
                m++;
            } else if(aux[m - l].compareTo(aux[n - l]) < 0) {
                arr[i] = aux[m - l];
                m++;
            } else {
                arr[i] = aux[n - l];
                n++;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] arr = sortingAdvance.mergeSortAdvance.SortTestHelper.generateRandomArray(100, 0, 100);
        MergeSort.sort(arr);
        SortTestHelper.printArray(arr);
    }
}
